Euler's Criterion

Theorem

Given an odd prime \(p\) and \(a \not\equiv 0 \pmod p\) then:

\[ x^2 \equiv a \pmod p \ \text{has a solution} \iff a^{\frac{p-1}{2}} \equiv 1 \pmod p\]

and

\[ x^2 \equiv a \pmod p \ \text{has no solution} \iff a^{\frac{p-1}{2}} \equiv -1 \pmod p.\]

Implicit in this is the claim that \(a^{\frac{p-1}{2}}\) has only two values \(1\) and \(-1\).

Proof

We will prove the first equivalence, and then prove that \(\{1, -1\}\) is exhaustively the set of possible values for \(a^{\frac{p - 1}{2}}\).

First let \(p\) be an odd prime and \(a\) an integer with \(a \not\equiv 0 \pmod p\). Then let \(x\) be a solution to:

\[ x^2 \equiv a \pmod p.\]

Since \(a\) is a quadratic residue, it can be expressed as an even power of a primitive root, so let \(a = g^{2k}\) for natural number \(k\) and primitive root modulo \(p\), \(g\).

Then,

\[ a^{\frac{p - 1}{2}} \equiv (g^{2k})^{\frac{p - 1}{2}} \equiv g^{p - 1} \equiv 1 \pmod p\]

by Fermat's little theorem.

For the converse, assume that \(a^{\frac{p - 1}{2}} \equiv 1 \pmod 1\) and now express \(a = g^n\) for some \(n \in \mathbb{N}\).

\[ 1 \equiv a^{\frac{p - 1}{2}} \equiv g^{n\frac{p - 1}{2}}.\]

Then, since the order of any element in multiplicative group of integers modulo \(p\) except for \(1\) is \(p - 1\), the group order, we know that:

\[ p - 1 \mid n\frac{p - 1}{2}.\]

We then have that:

\[\begin{align*} &p - 1 \mid n\frac{p - 1}{2} \\ \iff& \exists k \in \mathbb{Z}: k(p - 1) = n\frac{p - 1}{2} \\ \iff& \exists k \in \mathbb{Z}: k = \frac{n}{2} \\ \iff& \frac{n}{2} \in \mathbb{Z} \\ \iff& 2 \mid n \\ \end{align*}\]

and hence \(n\) is even. This means \(a = g^n\) is a primitive root, so:

\[ x^2 \equiv a \pmod p\]

has a solution in \(x\).

In General: \(a^{\frac{p - 1}{2}} = \pm 1\)

Finally we must show that in the other case, where the desired equation has no solutions, the only other possible value for \(a^{\frac{p - 1}{2}}\) is \(-1\).

This however is clear though since:

\[ (a^{\frac{p - 1}{2}})^2 \equiv a^{p - 1} \equiv 1 \pmod p\]

once again by Fermat's little theorem, and since for quadratic residues modulo a prime, there are only two square roots if one exists, one being the negative of the other, we know that:

\[ a^{\frac{p - 1}{2}} \equiv \pm 1 \pmod p.\]